﻿#pragma once
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>

#include "RecentCounter.h"
#include "DataType.h"

class LeetCode75
{
public:
    /*
    * 1768. 交替合并字符串
    * 给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
    */
    std::string mergeAlternately(std::string word1, std::string word2);

    /*
    * 1071. 字符串的最大公因子
    * 对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
    * 给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。
    */
    bool check(std::string dividend, std::string divisor);
    std::string gcdOfStrings(std::string str1, std::string str2);

    /*
    * 1431. 拥有最多糖果的孩子
    * 给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
    * 对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。
    */
    std::vector<bool> kidsWithCandies(std::vector<int>& candies, int extraCandies);

    /*
    * 605. 种花问题
    * 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
    * 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。
    * 另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
    */
    bool canPlaceFlowers(std::vector<int>& flowerbed, int n);

    /*
    * 345. 反转字符串中的元音字母
    * 给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
    * 元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。
    */
    bool isVowels(const char& ch);
    std::string reverseVowels(std::string s);

    /*
    * 151. 反转字符串中的单词
    * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
    * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
    * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
    * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
    */
    std::string reverseWords(std::string s);

    /*
    * 334. 递增的三元子序列
    * 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
    * 如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
    */
    bool increasingTriplet(std::vector<int>& nums);

    /*
    * 443. 压缩字符串
    * 给你一个字符数组 chars ，请使用下述算法压缩：
    * 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
    * 如果这一组长度为 1 ，则将字符追加到 s 中。
    * 否则，需要向 s 追加字符，后跟这一组的长度。
    * 压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。
    * 请在修改完输入数组后 ，返回该数组的新长度。
    * 你必须设计并实现一个只使用常量额外空间的算法来解决此问题。
    */
    int compress(std::vector<char>& chars);

    /*
    * 283. 移动零
    * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
    */
    void moveZeroes(std::vector<int>& nums);

    /*
    * 392. 判断子序列
    * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
    * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
    * （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
    */
    bool isSubsequence(std::string s, std::string t);

    /*
    * 1679. K 和数对的最大数目
    * 给你一个整数数组 nums 和一个整数 k 。
    * 每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
    * 返回你可以对数组执行的最大操作数。
    */
    int maxOperations(std::vector<int>& nums, int k);

    /*
    * 643. 子数组最大平均数 I
    * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
    * 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
    * 任何误差小于 10-5 的答案都将被视为正确答案。
    */
    double findMaxAverage(std::vector<int>& nums, int k);

    /*
    * 1456. 定长子串中元音的最大数目
    * 给你字符串 s 和整数 k 。
    * 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
    * 英文中的 元音字母 为（a, e, i, o, u）。
    */
    int maxVowels(std::string s, int k);

    /*
    * 1004. 最大连续1的个数 III
    * 给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
    */
    int longestOnes(std::vector<int>& nums, int k);

    /*
    * 1493. 删掉一个元素以后全为 1 的最长子数组
    * 给你一个二进制数组 nums ，你需要从中删掉一个元素。
    * 请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
    * 如果不存在这样的子数组，请返回 0 。
    */
    int longestSubarray(std::vector<int>& nums);

    /*
    * 1732. 找到最高海拔
    * 有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
    * 给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔。
    */
    int largestAltitude(std::vector<int>& gain);

    /*
    * 2215. 找出两数组的不同
    * 给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，请你返回一个长度为 2 的列表 answer ，其中：
    * answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。
    * answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。
    * 注意：列表中的整数可以按 任意 顺序返回。
    */
    std::vector<std::vector<int>> findDifference(std::vector<int>& nums1, std::vector<int>& nums2);

    /*
    * 1207. 独一无二的出现次数
    * 给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
    * 如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
    */
    bool uniqueOccurrences(std::vector<int>& arr);

    /*
    * 1657. 确定两个字符串是否接近
    * 如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
    * 操作 1：交换任意两个 现有 字符。
    * 例如，abcde -> aecdb
    * 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
    * 例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）
    * 你可以根据需要对任意一个字符串多次使用这两种操作。
    * 给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
    */
    bool closeStrings(std::string word1, std::string word2);

    /*
    * 2352. 相等行列对
    * 给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。
    * 如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。
    */
    int equalPairs(std::vector<std::vector<int>>& grid);
    bool equal(int row, int col, std::vector<std::vector<int>>& grid);

    /*
    * 2390. 从字符串中移除星号
    * 给你一个包含若干星号 * 的字符串 s 。
    * 在一步操作中，你可以：
    * 选中 s 中的一个星号。
    * 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
    * 返回移除 所有 星号之后的字符串。
    * 注意：
    * 生成的输入保证总是可以执行题面中描述的操作。
    * 可以证明结果字符串是唯一的。
    */
    std::string removeStars(std::string s);

    /*
    * 735. 小行星碰撞
    * 给定一个整数数组 asteroids，表示在同一行的小行星。
    * 对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。
    * 每一颗小行星以相同的速度移动。
    * 找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。
    * 如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。
    */
    std::vector<int> asteroidCollision(std::vector<int>& asteroids);

    /*
    * 394. 字符串解码
    * 给定一个经过编码的字符串，返回它解码后的字符串。
    * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
    * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
    * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
    */
    std::string getDigits(std::string& s, size_t& ptr);
    std::string getString(std::vector<std::string>& v);
    std::string decodeString(std::string s);

    /*
    * 649. Dota2 参议院
    * Dota2 的世界里有两个阵营：Radiant（天辉）和 Dire（夜魇）
    * Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
    * 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
    * 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。
    * 给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D'分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。
    * 以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
    * 假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。
    */
    std::string predictPartyVictory(std::string senate);

    /*
    * 2095. 删除链表的中间节点
    * 给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
    * 长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
    * 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
    */
    ListNode* deleteMiddle(ListNode* head);

    /*
    * 328. 奇偶链表
    * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
    * 第一个节点的索引被认为是 奇数，第二个节点的索引为 偶数 ，以此类推。
    * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
    * 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
    */
    ListNode* oddEvenList(ListNode* head);

    /*
    * 2130. 链表最大孪生和
    * 在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
    * 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
    * 孪生和 定义为一个节点和它孪生节点两者值之和。
    * 给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
    */
    int pairSum(ListNode* head);

    /*
    * 872. 叶子相似的树
    * https://leetcode.cn/problems/leaf-similar-trees/description/?envType=study-plan-v2&envId=leetcode-75
    * 请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列。
    * 举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
    * 如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
    * 如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
    */
    void dfs(TreeNode* node, std::vector<int>& seq);
    bool leafSimilar(TreeNode* root1, TreeNode* root2);

    /*
    * 1448. 统计二叉树中好节点的数目
    * https://leetcode.cn/problems/count-good-nodes-in-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75
    * 给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。
    *「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。
    */
    int goodNodes(TreeNode* root, int mx = INT_MIN);


    /*
    * 437. 路径总和 III
    * https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=leetcode-75
    * 给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。
    * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
    */
    int rootSum(TreeNode* root, long targetSum);
    int pathSum(TreeNode* root, int targetSum);

    /*
    * 1372. 二叉树中的最长交错路径
    * https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75
    * 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
    * 选择二叉树中 任意 节点和一个方向（左或者右）。
    * 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
    * 改变前进方向：左变右或者右变左。
    * 重复第二步和第三步，直到你在树中无法继续移动。
    * 交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
    * 请你返回给定树中最长交错路径的长度。
    */
    int dfs(TreeNode* root, int orient, int len);
    int longestZigZag(TreeNode* root);

    /*
    * 199. 二叉树的右视图
    * https://leetcode.cn/problems/binary-tree-right-side-view/description/?envType=study-plan-v2&envId=leetcode-75
    * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
    */
    std::vector<int> rightSideView(TreeNode* root);

    /*
    * 1161. 最大层内元素和
    * https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75
    * 给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
    * 请返回层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
    */
    int maxLevelSum(TreeNode* root);

    /*
    * 841. 钥匙和房间
    * https://leetcode.cn/problems/keys-and-rooms/?envType=study-plan-v2&envId=leetcode-75
    * 有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。
    *当你进入一个房间，你可能会在里面找到一套 不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。
    * 给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入 所有 房间返回 true，否则返回 false。
    */
    bool canVisitAllRooms(std::vector<std::vector<int>>& rooms);
    void dfsRoom(std::vector<std::vector<int>>& rooms, int roomIndex);
    std::vector<bool> m_visitRoom;
    int m_roomNum;

    /*
    * 547. 省份数量
    * https://leetcode.cn/problems/number-of-provinces/description/?envType=study-plan-v2&envId=leetcode-75
    * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
    * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
    * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
    * 返回矩阵中 省份 的数量。
    */
    int findCircleNum(std::vector<std::vector<int>>& isConnected);
    void dfsCity(std::vector<std::vector<int>>& isConnected, std::vector<bool>& isVisited, int cityCount, int i);

    /*
    * 1466. 重新规划路线
    * https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/?envType=study-plan-v2&envId=leetcode-75
    * n 座城市，从 0 到 n-1 编号，其间共有 n-1 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。
    * 路线用 connections 表示，其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。
    * 今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。
    * 请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。
    * 题目数据 保证 每个城市在重新规划路线方向后都能到达城市 0 。
    */
    int minReorder(int n, std::vector<std::vector<int>>& connections);
};